/*
 * Glouton.cpp
 *
 *  Created on: 10 nov. 2011
 *  Authors: bnoleau, cybourdi, rlecrois
 */

#include "Glouton.h"

Glouton::Glouton() {
}

Glouton::~Glouton() {
}

list<int> Glouton::vertexCover(Graph* g) {
	list<int> cover;
	if (g->numberOfEdge() > 0) {
		Node* maxDegree = searchMaxDegree(g);
		while (maxDegree->outDeg() > 0) {
			g->eraseEdgesOfNode(maxDegree);
			maxDegree->getEdgeList()->clear();
			cover.push_back(maxDegree->getID());
			maxDegree = searchMaxDegree(g);
		}
	}
	return cover;
}

Node* Glouton::searchMaxDegree(Graph* g) {
	Node* maxDegree = g->nodeAt(0);

	for (int i = 0; i < g->numberOfNode(); i++) {
		Node* currentNode = g->nodeAt(i);
		if (currentNode->outDeg() > maxDegree->outDeg())
			maxDegree = currentNode;
	}
	return maxDegree;
}

